import com.sun.javafx.image.IntPixelGetter;

import java.util.List;
import java.util.Random;
import java.util.Stack;

/**
 * @author Eric Wu
 * @since 1.8
 * create on 2018.09.29
 */
public class BinaryTree<T> {

    private Node<T> root = null;

    public BinaryTree() {
        root = new Node<>();
    }

    public BinaryTree(T data) {
        root = new Node<>(data);
    }

    /**
     * Gets the value of root.
     *
     * @return the value of root
     */
    public Node<T> getRoot() {
        return root;
    }

    /**
     * Sets the root.
     *
     * <p>You can use getRoot() to get the value of root</p>
     *
     * @param root root
     */
    public void setRoot(Node<T> root) {
        this.root = root;
    }

    public void preTravel(IVisitNode<T> visitNode) {

        Stack<Node<T>> stack = new Stack<>();
        Node<T> p = root;

        while (true) {

            if (p != null) {
                visitNode.visited(p);

            } else {
                if (stack.isEmpty()) {
                    break;
                }
                p = stack.pop().getRight();
                continue;
            }
            if (p.getLeft() != null) {
                stack.push(p);
                p = p.getLeft();
            } else if (p.getRight() != null) {
                p = p.getRight();
            } else {
                p = null;
            }

        }


    }

    public void midTravel(IVisitNode<T> visitNode) {

        if (visitNode == null) {
            return;
        }

        Stack<Node<T>> stack = new Stack<>();
        Node<T> node = root;

        while (true) {

            if(node == null){
                if(stack.isEmpty()){
                    break;
                }
                //处理stack不为空的
                node = stack.pop();
                visitNode.visited(node);
                node = node.getRight();
                continue;

            }
            if(node.getLeft()!= null){
                stack.push(node);
                node = node.getLeft();
            }else if(node.getLeft() == null){
                visitNode.visited(node);
                node = node.getRight();

            }

        }

    }

    public void postTravel(IVisitNode<T> visitNode) {

    }

    public void preTravelCur(IVisitNode<T> visitNode) {
        if (visitNode == null) {
            return;
        }

        preVisited(root, visitNode);
    }

    public void midTravelCur(IVisitNode<T> visitNode) {

        if (visitNode == null) {
            return;
        }

        midVisited(root, visitNode);

    }

    private void preVisited(Node<T> node, IVisitNode<T> visitNode) {

        if (node == null) {
            return;
        }

        visitNode.visited(node);

        preVisited(node.getLeft(), visitNode);
        preVisited(node.getRight(), visitNode);
    }

    private void midVisited(Node<T> node, IVisitNode visitNode) {

        if (node == null || visitNode == null) {
            return;
        }

        midVisited(node.getLeft(), visitNode);
        visitNode.visited(node);
        midVisited(node.getRight(), visitNode);

    }


    public static void main(String[] args) {

        BinaryTree<Integer> binaryTree = new BinaryTree<>(0);

        Random random = new Random();

        for (int i = 1; i <= 9; i++) {

            Node<Integer> node = new Node<>(i);
            Node<Integer> root = binaryTree.getRoot();


            while (true) {
                int flag = random.nextInt(2);
                if (flag == 0 && root.getLeft() == null) {
                    root.setLeft(node);
                    break;
                } else if (flag == 1 && root.getRight() == null) {
                    root.setRight(node);
                    break;
                }
                root = flag == 0 ? root.getLeft() : root.getRight();
            }

        }


        System.out.println("PRE ==============================");
        binaryTree.preTravelCur(new IVisitNode<Integer>() {
            @Override
            public void visited(Node<Integer> node) {
                System.out.println(node.getData() + " ");
            }
        });
        System.out.println("----------------------------------");

        binaryTree.preTravel(new IVisitNode<Integer>() {
            @Override
            public void visited(Node<Integer> node) {
                System.out.println(node.getData() + " ");
            }
        });


        System.out.println("===================================\n");


        System.out.println("MID ==================================");

        binaryTree.midTravelCur(new IVisitNode<Integer>() {
            @Override
            public void visited(Node<Integer> node) {
                System.out.println(node.getData());
            }
        });

        System.out.println("------------------------------------");

        binaryTree.midTravel(new IVisitNode<Integer>() {
            @Override
            public void visited(Node<Integer> node) {
                System.out.println(node.getData());
            }
        });
    }
}
